home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 2: Applications / Linux Cubed Series 2 - Applications.iso / circuits / irsim-9.000 / irsim-9 / src / irsim / nsubrs.c < prev    next >
C/C++ Source or Header  |  1994-07-21  |  11KB  |  472 lines
  1. /* 
  2.  *     ********************************************************************* 
  3.  *     * Copyright (C) 1988, 1990 Stanford University.                     * 
  4.  *     * Permission to use, copy, modify, and distribute this              * 
  5.  *     * software and its documentation for any purpose and without        * 
  6.  *     * fee is hereby granted, provided that the above copyright          * 
  7.  *     * notice appear in all copies.  Stanford University                 * 
  8.  *     * makes no representations about the suitability of this            * 
  9.  *     * software for any purpose.  It is provided "as is" without         * 
  10.  *     * express or implied warranty.  Export of this software outside     * 
  11.  *     * of the United States of America may require an export license.    * 
  12.  *     ********************************************************************* 
  13.  */
  14.  
  15. #include <stdio.h>
  16. #include "defs.h"
  17. #include "net.h"
  18. #include "globals.h"
  19.  
  20. /* useful subroutines for dealing with network */
  21.  
  22. public    char   vchars[] = "0XX1";
  23.  
  24. public    char  *ttype[ NTTYPES ] =
  25.   {
  26.     "n-channel",
  27.     "p-channel",
  28.     "depletion",
  29.     "resistor"
  30.   };
  31.  
  32.  
  33. #define    HASHSIZE        4387    /* hash table size */
  34. #define    NBIT_HASH        14    /* number of bits for HASHSIZE */
  35.  
  36. private    nptr  hash[HASHSIZE];
  37.  
  38.  
  39. public int GetHashSize()
  40.   {
  41.     return( HASHSIZE );
  42.   }
  43.  
  44.  
  45. /* hashing function used in interning symbols */
  46. private    char  lcase[128] = 
  47.   {
  48.     0,        01,    02,    03,    04,    05,    06,    07,
  49.     010,    011,    012,    013,    014,    015,    016,    017,
  50.     020,    021,    022,    023,    024,    025,    026,    027,
  51.     030,    031,    032,    033,    034,    035,    036,    037,
  52.     ' ',    '!',    '"',    '#',    '$',    '%',    '&',    047,
  53.     '(',    ')',    '*',    '+',    ',',    '-',    '.',    '/',
  54.     '0',    '1',    '2',    '3',    '4',    '5',    '6',    '7',
  55.     '8',    '9',    ':',    ';',    '<',    '=',    '>',    '?',
  56.     '@',    'a',    'b',    'c',    'd',    'e',    'f',    'g',
  57.     'h',    'i',    'j',    'k',    'l',    'm',    'n',    'o',
  58.     'p',    'q',    'r',    's',    't',    'u',    'v',    'w',
  59.     'x',    'y',    'z',    '[',    0134,    ']',    '^',    '_',
  60.     '`',    'a',    'b',    'c',    'd',    'e',    'f',    'g',
  61.     'h',    'i',    'j',    'k',    'l',    'm',    'n',    'o',
  62.     'p',    'q',    'r',    's',    't',    'u',    'v',    'w',
  63.     'x',    'y',    'z',    '{',    '|',    '}',    '~',    0177
  64.   };
  65.  
  66.  
  67.  
  68. private int sym_hash( name )
  69.   register char  *name;
  70.   {
  71.     register int  hashcode = 0;
  72.  
  73.     do
  74.     hashcode = (hashcode << 1) ^ (*name | 0x20);
  75.     while( *(++name) );
  76.     return( ((hashcode >= 0) ? hashcode : ~hashcode) % HASHSIZE );
  77.   }
  78.  
  79.  
  80. /*
  81.  * Compare 2 strings, case doesn't matter.  Return value is an integer greater
  82.  * than, equal to, or less than 0, according as 's1' is lexicographically
  83.  * greater than, equal to, or less than 's2'.
  84.  */
  85. public int str_eql( s1, s2 )
  86.   register char  *s1, *s2;
  87.   {
  88.     register int  cmp;
  89.  
  90.     while( *s1 )
  91.       {
  92.     if( (cmp = lcase[*s1++] - lcase[*s2++]) != 0 )
  93.         return( cmp );
  94.       }
  95.     return( 0 - *s2 );
  96.   }
  97.  
  98.  
  99. /* compare pattern with string, case doesn't matter.  "*" wildcard accepted */
  100. public int str_match( p, s )
  101.   register char  *p, *s;
  102.   {
  103.     while( 1 )
  104.       {
  105.     if( *p == '*' )
  106.       {
  107.         /* skip past multiple wildcards */
  108.         do
  109.         p++;
  110.         while( *p == '*' );
  111.  
  112.         /* if pattern ends with wild card, automatic match */
  113.         if( *p == 0 )
  114.         return( 1 );
  115.  
  116.         /* *p now points to first non-wildcard character, find matching
  117.          * character in string, then recursively match remaining pattern.
  118.          * if recursive match fails, assume current '*' matches more...
  119.          */
  120.         while( *s != 0 )
  121.           {
  122.         while( lcase[*s] != lcase[*p] )
  123.             if( *s++ == 0 )
  124.             return( 0 );
  125.         if( str_match( p + 1, ++s ) )
  126.             return( 1 );
  127.           }
  128.  
  129.         /* couldn't find matching character after '*', no match */
  130.         return( 0 );
  131.       }
  132.     else if( *p == 0 )
  133.         return( *s == 0 );
  134.     else if( lcase[*p++] != lcase[*s++] )
  135.         return( 0 );
  136.       }
  137.   }
  138.  
  139.  
  140. /* find node in network */
  141. public nptr find( name )
  142.   register char  *name;
  143.   {
  144.     register nptr  ntemp;
  145.     register int   cmp = 1;
  146.  
  147.     if( txt_coords and name[0] == '@' and name[1] == '=' )
  148.     if( (ntemp = FindNode_TxtorPos( name )) != NULL )
  149.         return( ntemp );
  150.  
  151.     for( ntemp = hash[sym_hash( name )]; ntemp != NULL; ntemp = ntemp->hnext )
  152.       {
  153.     if( (cmp = str_eql( name, ntemp->nname )) >= 0 )
  154.         break;
  155.       }
  156.     return( (cmp == 0) ? ntemp : NULL );
  157.   }
  158.  
  159.  
  160. /*
  161.  * Get node structure.  If not found, create a new one.
  162.  * If create is TRUE a new node is created and NOT entered into the table.
  163.  */
  164. public nptr GetNode( name )
  165.   register char  *name;
  166.   {
  167.     register nptr  n, *prev;
  168.     register int   i;
  169.  
  170.     prev = &hash[ sym_hash( name ) ];
  171.     for( i = 1, n = *prev; n != NULL; n = *(prev = &n->hnext) )
  172.     if( (i = str_eql( name, n->nname )) >= 0 )
  173.         break;
  174.  
  175.     if( i == 0 )
  176.       {
  177.     if( strcmp( name, n->nname ) != 0 )
  178.         fprintf( stderr, "Warning: Aliasing nodes '%s' and '%s'\n",
  179.           name, n->nname );
  180.     while( n->nflags & ALIAS )
  181.         n = n->nlink;
  182.     return( n );
  183.       }
  184.  
  185.     /* allocate new node from free storage */
  186.     if( (n = (nptr) freeNodes) == NULL )
  187.     n = (nptr) MallocList( sizeof( struct Node ), 1 );
  188.     freeNodes = n->nlink;
  189.  
  190.     nnodes++;
  191.  
  192.     n->hnext = *prev;    /* insert node into hash table, after prev */
  193.     *prev = n;
  194.  
  195.     /* initialize node entries */
  196.     n->ngate = n->nterm = NULL;
  197.     n->nflags = 0;
  198.     n->ncap = MIN_CAP;
  199.     n->vlow = LOWTHRESH;
  200.     n->vhigh = HIGHTHRESH;
  201.     n->c.time = 0;
  202.     n->tplh = 0;
  203.     n->tphl = 0;
  204.     n->t.cause = NULL;
  205.     n->nlink = NULL;
  206.     n->events = NULL;
  207.     n->npot = X;
  208.  
  209.     n->head.next = last_hist;
  210.     n->head.time = 0;
  211.     n->head.val = X;
  212.     n->head.inp = 0;
  213.     n->head.punt = 0;
  214.     n->head.t.r.rtime = n->head.t.r.delay = 0;
  215.     n->curr = &(n->head);
  216.  
  217.     /* store all node-names as strings */
  218.     i = strlen( name ) + 1;
  219.     n->nname = Valloc( i, 1 );
  220.     bcopy( name, n->nname, i );
  221.  
  222.     return( n );
  223.   }
  224.  
  225.  
  226. public nptr GetNewNode( name )
  227.   char  *name;
  228.   {
  229.     register nptr  n;
  230.     int            i;
  231.  
  232.     if( VDD_node != NULL and str_eql( name, pnode( VDD_node ) ) == 0 )
  233.     return( VDD_node );
  234.     if( GND_node != NULL and str_eql( name, pnode( GND_node ) ) == 0 )
  235.     return( GND_node );
  236.  
  237.     if( (n = (nptr) freeNodes) == NULL )
  238.     n = (nptr) MallocList( sizeof( struct Node ), 1 );
  239.     freeNodes = n->nlink;
  240.  
  241.     nnodes++;
  242.  
  243.     n->hnext = n;    /* node NOT inserted in hash-table */
  244.  
  245.     n->ngate = n->nterm = NULL;
  246.     n->nflags = 0;
  247.     n->ncap = MIN_CAP;
  248.     n->vlow = LOWTHRESH;
  249.     n->vhigh = HIGHTHRESH;
  250.     n->c.time = 0;
  251.     n->tplh = 0;
  252.     n->tphl = 0;
  253.     n->t.cause = NULL;
  254.     n->nlink = NULL;
  255.     n->events = NULL;
  256.     n->npot = X;
  257.  
  258.     n->head.next = last_hist;
  259.     n->head.time = 0;
  260.     n->head.val = X;
  261.     n->head.inp = 0;
  262.     n->head.punt = 0;
  263.     n->head.t.r.rtime = n->head.t.r.delay = 0;
  264.     n->curr = &(n->head);
  265.  
  266.     /* store all node-names as strings */
  267.     i = strlen( name ) + 1;
  268.     n->nname = Valloc( i, 1 );
  269.     bcopy( name, n->nname, i );
  270.  
  271.     return( n );
  272.   }
  273.  
  274.  
  275. /* insert node into hash table.  Keep table entry sorted in ascending order */
  276. public void n_insert( nd )
  277.   register nptr  nd;
  278.   {
  279.     register nptr  n, *prev;
  280.     register char  *name;
  281.     register int   i = 1;
  282.  
  283.     name = pnode( nd );
  284.     prev = &hash[ sym_hash( name ) ];
  285.     for( n = *prev; n != NULL; n = *(prev = &n->hnext) )
  286.       {
  287.     i = str_eql( name, n->nname );
  288.     if( i >= 0 )
  289.         break;
  290.       }
  291.     if( i == 0 )
  292.       {
  293.     if( n != nd )
  294.         lprintf( stderr, "n_insert: multiple node '%s'\n", pnode( nd ) );
  295.     return;
  296.       }
  297.     nd->hnext = *prev;
  298.     *prev = nd;
  299.   }
  300.  
  301.  
  302. /*
  303.  * Delete node from hash table, and free its name.
  304.  */
  305. public void n_delete( nd )
  306.   register nptr  nd;
  307.   {
  308.     register nptr  n, *prev;
  309.  
  310.     prev = &hash[ sym_hash( pnode( nd ) ) ];
  311.     for( n = *prev; n != NULL ; n = *(prev = &n->hnext) )
  312.       {
  313.     if( n == nd )
  314.       {
  315.         Vfree( n->nname );
  316.         n->nname = NULL;
  317.         *prev = n->hnext;
  318.         n->hnext = n;        /* mark node not in hash-table */
  319.         return;
  320.       }
  321.       }
  322.   }
  323.  
  324.  
  325. /*
  326.  * Visit each node in network, calling function passed.
  327.  * If 'fun' returns anything <> 0 then terminate prematurely.
  328.  */
  329. public void walk_net( fun, arg )
  330.   int   (*fun)();
  331.   char  *arg;
  332.   {
  333.     register int   index;
  334.     register nptr  n;
  335.  
  336.     for( index = 0; index < HASHSIZE; index++ )
  337.     for( n = hash[index]; n; n = n->hnext )
  338.         if( (*fun)( n, arg ) )
  339.         return;
  340.   }
  341.  
  342.  
  343. /*
  344.  * Visit each node in network, calling function passed with arguments:
  345.  *    node    -> the current node.
  346.  *    index    -> number that identifies node in the hash-table.
  347.  *    arg    -> whatever argument the caller provided.
  348.  * If 'fun' returns FALSE then terminate prematurely.
  349.  */
  350. public void walk_net_index( fun, arg )
  351.   int   (*fun)();
  352.   char  *arg;
  353.   {
  354.     register Uint  mi, ma;
  355.     register nptr  n;
  356.  
  357.     for( ma = 0; ma < HASHSIZE; ma++ )
  358.     for( n = hash[ ma ], mi = 0; n; n = n->hnext, mi++ )
  359.       {
  360.         Ulong  val = (mi << NBIT_HASH) | ma;
  361.         if( (*fun)( n, val, arg ) )
  362.         return;
  363.       }
  364.   }
  365.  
  366.  
  367. /*
  368.  * Return a list of all nodes in the network.
  369.  */
  370. public nptr GetNodeList()
  371.   {
  372.     register int   index;
  373.     register nptr  n, *last;
  374.     struct Node    head;
  375.  
  376.     last = &(head.n.next);
  377.     for( index = 0; index < HASHSIZE; index++ )
  378.       {
  379.     for( n = hash[index]; n != NULL; n = n->hnext )
  380.       {
  381.         *last = n;
  382.         last = &(n->n.next);
  383.       }
  384.       }
  385.     *last = NULL;
  386.     return( head.n.next );
  387.   }
  388.  
  389.  
  390. /*
  391.  * Return the node corresponding to the index number (returned by Node2index).
  392.  */
  393. public nptr Index2node( index )
  394.   Ulong  index;
  395.   {
  396.     register nptr  n;
  397.     register unsigned  ma, mi;
  398.  
  399.     ma = index & ((1 << NBIT_HASH) - 1);
  400.     mi = index >> NBIT_HASH;
  401.     if( ma >= HASHSIZE )
  402.     return( NULL );
  403.     for( n = hash[ ma ]; n != NULL and mi != 0; n = n->hnext, mi-- );
  404.     return( n );
  405.   }
  406.  
  407.  
  408. /*
  409.  * Return a number that identifies the node in the name hash-table.
  410.  */
  411. public Ulong Node2index( nd )
  412.   nptr  nd;
  413.   {
  414.     register nptr      n;
  415.     register unsigned  mi, ma;
  416.     Ulong              val;
  417.  
  418.     if( nd != NULL )
  419.       {
  420.     ma = sym_hash( pnode( nd ) );
  421.     for( n = hash[ ma ], mi = 0; n != NULL; n = n->hnext, mi++ )
  422.       {
  423.         if( n == nd )
  424.         goto got_it;
  425.       }
  426.       }
  427.     ma = HASHSIZE;
  428.     mi = 0;
  429.  
  430.   got_it :
  431.     val = (mi << NBIT_HASH) | ma;
  432.     return( val );
  433.   }
  434.  
  435.  
  436. /* visit each node in network, calling function passed as arg with any node
  437.  * whose name matches pattern
  438.  */
  439. public int match_net( pattern, fun, arg )
  440.   char  *pattern;
  441.   int   (*fun)();
  442.   char  *arg;
  443.   {
  444.     register int   index;
  445.     register nptr  n;
  446.     int            total = 0;
  447.  
  448.     for( index = 0; index < HASHSIZE; index++ )
  449.     for( n = hash[index]; n; n = n->hnext )
  450.         if( str_match( pattern, pnode( n ) ) )
  451.         total += (*fun)( n, arg );
  452.  
  453.     return( total );
  454.   }
  455.  
  456.  
  457. /* return pointer to asciz name of node */
  458.  
  459. public
  460. #define    pnode( NODE )    ( (NODE)->nname )
  461.  
  462.  
  463.  
  464. /* initialize hash table */
  465. public void init_hash()
  466.   {
  467.     register int  i;
  468.  
  469.     for( i = 0; i < HASHSIZE; i += 1 )
  470.     hash[i] = NULL;
  471.   }
  472.